<!doctype html public "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!--

Generated from t-y-scheme.tex by tex2page, v 20070609
(running on MzScheme 4.2.1, unix), 
(c) Dorai Sitaram, 
http://www.ccs.neu.edu/~dorai/tex2page/tex2page-doc.html

-->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>
Teach Yourself Scheme in Fixnum Days 中文版
</title>
<link rel="stylesheet" type="text/css" href="t-y-scheme-Z-S.css" title=default>
<meta name="robots" content="index,follow">
<meta name=description content="A practical
introduction to the programming language Scheme">

<meta name=author content="Dorai Sitaram">

<link rev=made href="mailto:dorai @ ccs.neu.edu">
</head>
<body>
<div id=slidecontent>
<div align=right class=navigation>[Go to <span><a href="t-y-scheme.html">first</a>, <a href="t-y-scheme-Z-H-15.html">previous</a></span><span>, <a href="t-y-scheme-Z-H-17.html">next</a></span> page<span>; &nbsp;&nbsp;</span><span><a href="t-y-scheme-Z-H-1.html#node_toc_start">contents</a></span><span><span>; &nbsp;&nbsp;</span><a href="t-y-scheme-Z-H-25.html#node_index_start">index</a></span>]</div>
<p></p>
<a name="node_chap_14"></a>
<h1 class=chapter>
<div class=chapterheading><a href="t-y-scheme-Z-H-1.html#node_toc_node_chap_14">Chapter 14</a></div><br>
<a href="t-y-scheme-Z-H-1.html#node_toc_node_chap_14">不确定性</a></h1>
<p><a name="node_idx_466"></a><a name="node_idx_468"></a><a name="node_idx_470"></a>McCarthy 的不确定性运算符 <code class=scheme><span class=keyword>amb</span></code> [<a href="t-y-scheme-Z-H-24.html#node_bib_25">25</a>,&nbsp;<a href="t-y-scheme-Z-H-24.html#node_bib_4">4</a>,&nbsp;<a href="t-y-scheme-Z-H-24.html#node_bib_33">33</a>] 和 Lisp 本身一样古老，虽然它没有在 Lisp 中提供。<code class=scheme><span class=keyword>amb</span></code> 接受 0 个或更多的表达式作为参数，然后在它们中间做一个不确定选择，<strike>偏向于那些使程序更有意义的选项</strike>。这里我们将要探索 Scheme 内建的 <code class=scheme><span class=keyword>amb</span></code>，它在不确定的选择中做出一个深度优先的选择，并且使用 Scheme 的控制运算符 <code class=scheme><span class=variable>call/cc</span></code> 来回溯到其他选项。结果是一个优雅的回溯策略，这种策略用于在 Scheme 里面直接在问题空间中搜索而不求助于扩充的语言。它检索这种用于实现 Prolog 风格的逻辑编程[<a href="t-y-scheme-Z-H-24.html#node_bib_16">16</a>,&nbsp;<a href="t-y-scheme-Z-H-24.html#node_bib_7">7</a>]的继续策略。但它更节省，因为这个运算符类似于 Scheme 布尔运算符，在运行时不要求特殊的环境，也不依赖那些像逻辑变量和统一的语言基本构造。</p>
<p>
</p>
<a name="node_sec_14.1"></a>
<h2 class=section><a href="t-y-scheme-Z-H-1.html#node_toc_node_sec_14.1">14.1&nbsp;&nbsp;<code class=scheme><span class=keyword>amb</span></code> 的描述</a></h2>
<p><code class=scheme><span class=keyword>amb</span></code> 的易懂的描述和许多使用的示例可以在 Scheme 教科书 SICP [<a href="t-y-scheme-Z-H-24.html#node_bib_1">1</a>] 中找到。<code class=scheme><span class=keyword>amb</span></code> 常接受 0 个或者更多的变量，然后不确定地返回他们中<em>某一个</em>的值。所以，</p>
<p>
</p>
<pre class=scheme>(<span class=keyword>amb</span> <span class=selfeval>1</span> <span class=selfeval>2</span>)
</pre><p></p>
<p>
</p>

<p class=noindent>可能返回 1 <em>或者</em> 2。</p>
<p><code class=scheme><span class=keyword>amb</span></code> 调用时没有后接表达式就没有值可以返回，就被认为是<em>失败的</em>。所以，</p>
<p>
</p>
<pre class=scheme>(<span class=keyword>amb</span>)
<span style="color: red"><tt><strong><i>--&gt;ERROR!!!</i></strong></tt></span> <span class=keyword>amb</span> <span class=variable>tree</span> <span class=variable>exhausted</span>
</pre><p></p>
<p>
</p>

<p class=noindent>（我们等会再来检查失败信息中的措辞。）</p>
<p>特别地，如果至少它的某个子表达式收敛（converge）了，也就是没有失败，<code class=scheme><span class=keyword>amb</span></code> 要求有一个返回值。所以，</p>
<p>
</p>
<pre class=scheme>(<span class=keyword>amb</span> <span class=selfeval>1</span> (<span class=keyword>amb</span>))
</pre><p></p>
<p>
</p>

<p class=noindent>和</p>
<p>
</p>
<pre class=scheme>(<span class=keyword>amb</span> (<span class=keyword>amb</span>) <span class=selfeval>1</span>)
</pre><p></p>
<p>
</p>

<p class=noindent>都返回 1。</p>
<p>很显然，<code class=scheme><span class=keyword>amb</span></code> 不能只对它的第一个子表达式求值，因为它必须尽可能地返回一个<em>未失败</em>的值。但还没完，对于<code class=scheme><span class=keyword>amb</span></code> 的局部选择而言，收敛更加重要。<code class=scheme><span class=keyword>amb</span></code> 应该返回<em>那个</em>收敛的值使得<em>整个程序</em>都收敛。在某些说法中，<code class=scheme><span class=keyword>amb</span></code> 是一个<em>天使一样的</em>运算符。</p>
<p>例如，</p>
<p>
</p>
<pre class=scheme>(<span class=keyword>amb</span> <span class=selfeval>#f</span> <span class=selfeval>#t</span>)
</pre><p></p>
<p>
</p>

<p class=noindent>可能既返回 <code class=scheme><span class=selfeval>#f</span></code> 或者 <code class=scheme><span class=selfeval>#t</span></code>，但在程序</p>
<p>
</p>
<pre class=scheme>(<span class=keyword>if</span> (<span class=keyword>amb</span> <span class=selfeval>#f</span> <span class=selfeval>#t</span>)
    <span class=selfeval>1</span>
    (<span class=keyword>amb</span>))
</pre><p></p>
<p>
</p>

<p class=noindent>中，第一个 <code class=scheme><span class=keyword>amb</span></code> 表达式<em>一定</em>返回 <code class=scheme><span class=selfeval>#t</span></code>。如果它返回了 <code class=scheme><span class=selfeval>#f</span></code>，<code class=scheme><span class=keyword>if</span></code> 的 “else” 分支将被选中，使得整个程序失败。</p>
<p>
</p>
<a name="node_sec_14.2"></a>
<h2 class=section><a href="t-y-scheme-Z-H-1.html#node_toc_node_sec_14.2">14.2&nbsp;&nbsp;在 Scheme 中实现 <code class=scheme><span class=keyword>amb</span></code></a></h2>
<p>在我们的 <code class=scheme><span class=keyword>amb</span></code> 实现中，我们将会从左到右检查 <code class=scheme><span class=keyword>amb</span></code> 的子表达式。也就是，在第一个子表达式选中时，如果它导致了整体的失败，将去查看第二个，如此下去。在回溯到前一个 <code class=scheme><span class=keyword>amb</span></code> 之前，将去搜索程序控制流程中后出现的 <code class=scheme><span class=keyword>amb</span></code>。也就是说，在 <code class=scheme><span class=keyword>amb</span></code><em>选择树</em>中我们实施了一个深度优先搜索，当我们碰到失败点时，我们回到树中能提供更多选择的最近节点。（这称为<em>时序回溯法</em>。）</p>
<p>我们首先定义一个设置失败继续的基本机制</p>
<p>
</p>
<pre class=scheme>(<span class=keyword>define</span> <span class=variable>amb-fail</span> <span class=keyword>'</span><span class=variable>*</span>)

(<span class=keyword>define</span> <span class=variable>initialize-amb-fail</span>
  (<span class=keyword>lambda</span> ()
    (<span class=keyword>set!</span> <span class=variable>amb-fail</span>
      (<span class=keyword>lambda</span> ()
        (<span class=variable>error</span> <span class=selfeval>&quot;amb tree exhausted&quot;</span>)))))

(<span class=variable>initialize-amb-fail</span>)
</pre><p></p>
<p>
</p>

<p class=noindent>当 <code class=scheme><span class=keyword>amb</span></code> 失败并来到 <code class=scheme><span class=variable>amb-fail</span></code> 时会碰到继续运行的边界。当 <code class=scheme><span class=keyword>amb</span></code> 选择树所有部分都尝试过但发现失败的时候，这个继续过程将会被调用。</p>
<p>我们把 <code class=scheme><span class=keyword>amb</span></code> 定义为一个宏，它数目不定的子表达式。</p>
<p>
</p>
<pre class=scheme>(<span class=keyword>define-macro</span> <span class=keyword>amb</span>
  (<span class=keyword>lambda</span> <span class=variable>alts...</span>
    <span class=keyword>`</span>(<span class=keyword>let</span> ((<span class=variable>+prev-amb-fail</span> <span class=variable>amb-fail</span>))
       (<span class=variable>call/cc</span>
        (<span class=keyword>lambda</span> (<span class=variable>+sk</span>)

          <span class=keyword>,@</span>(<span class=variable>map</span> (<span class=keyword>lambda</span> (<span class=variable>alt</span>)
                   <span class=keyword>`</span>(<span class=variable>call/cc</span>
                     (<span class=keyword>lambda</span> (<span class=variable>+fk</span>)
                       (<span class=keyword>set!</span> <span class=variable>amb-fail</span>
                         (<span class=keyword>lambda</span> ()
                           (<span class=keyword>set!</span> <span class=variable>amb-fail</span> <span class=variable>+prev-amb-fail</span>)
                           (<span class=variable>+fk</span> <span class=keyword>'</span><span class=variable>fail</span>)))
                       (<span class=variable>+sk</span> <span class=keyword>,</span><span class=variable>alt</span>))))
                 <span class=variable>alts...</span>)

          (<span class=variable>+prev-amb-fail</span>))))))
</pre><p></p>
<p>
</p>

<p class=noindent>对 <code class=scheme><span class=keyword>amb</span></code> 的调用首先把 <code class=scheme><span class=variable>amb-fail</span></code> 的值存到 <code class=scheme><span class=variable>+prev-amb-fail</span></code> 中，这个值在入口的时候是变化的。因为 <code class=scheme><span class=variable>amb-fail</span></code> 变量将会在众多的测试中被设成不同的失败继续。</p>
<p>然后我们得到了 <code class=scheme><span class=keyword>amb</span></code> 的<em>入口</em>继续 <code class=scheme><span class=variable>+sk</span></code>，所以当某个测试求值为未失败的值时，可以马上结束 <code class=scheme><span class=keyword>amb</span></code>。</p>
<p>每一个交替测试 <code class=scheme><span class=variable>alt</span></code> 按顺序（Scheme 中非显性的 <code class=scheme><span class=keyword>begin</span></code> 序列）被测试。</p>
<p>首先我们得到了现在的继续过程 <code class=scheme><span class=variable>+fk</span></code>，把它包含在一个过程中，把 <code class=scheme><span class=variable>amb-fail</span></code> 设置为那个过程。测试的将用 <code class=scheme>(<span class=variable>+sk</span> <span class=variable>alt</span>)</code> 来求值。如果 <code class=scheme><span class=variable>alt</span></code> 求值没有失败，它的返回值将给继续过程 <code class=scheme><span class=variable>+sk</span></code>，过程将马上结束 <code class=scheme><span class=keyword>amb</span></code> 调用。如果 <code class=scheme><span class=variable>alt</span></code> 失败了，它调用 <code class=scheme><span class=variable>amb-fail</span></code>。<code class=scheme><span class=variable>amb-fail</span></code> 的第一个任务是重置 <code class=scheme><span class=variable>amb-fail</span></code> 为它在入口时候的值。然后它调用失败继续 <code class=scheme><span class=variable>+fk</span></code>，失败继续将去进行下一个测试，如果有的话。</p>
<p>如果所有的测试都失败了，在 <code class=scheme><span class=keyword>amb</span></code> 入口的 <code class=scheme><span class=variable>amb-fail</span></code>，我们以前存到了变量 <code class=scheme><span class=variable>+prev-amb-fail</span></code> 中，将会调用。</p>
<p>
</p>
<a name="node_sec_14.3"></a>
<h2 class=section><a href="t-y-scheme-Z-H-1.html#node_toc_node_sec_14.3">14.3&nbsp;&nbsp;在 Scheme 中使用 <code class=scheme><span class=keyword>amb</span></code></a></h2>
<p>在 1 到 10 中选一个数，可以这样</p>
<p>
</p>
<pre class=scheme>(<span class=keyword>amb</span> <span class=selfeval>1</span> <span class=selfeval>2</span> <span class=selfeval>3</span> <span class=selfeval>4</span> <span class=selfeval>5</span> <span class=selfeval>6</span> <span class=selfeval>7</span> <span class=selfeval>8</span> <span class=selfeval>9</span> <span class=selfeval>10</span>)
</pre><p></p>
<p>
</p>

<p class=noindent>确切些，作为一个程序的话它将得到 1，但根据上下文来说，它将返回上面的任何一个数。</p>
<p>过程 <code class=scheme><span class=variable>number-between</span></code> 用了一个更抽象的方法来产生一个从 <code class=scheme><span class=variable>lo</span></code> 到 <code class=scheme><span class=variable>hi</span></code> （包含 hi）的数字：</p>
<p>
</p>
<pre class=scheme>(<span class=keyword>define</span> <span class=variable>number-between</span>
  (<span class=keyword>lambda</span> (<span class=variable>lo</span> <span class=variable>hi</span>)
    (<span class=keyword>let</span> <span class=variable>loop</span> ((<span class=variable>i</span> <span class=variable>lo</span>))
      (<span class=keyword>if</span> (<span class=variable>&gt;</span> <span class=variable>i</span> <span class=variable>hi</span>) (<span class=keyword>amb</span>)
          (<span class=keyword>amb</span> <span class=variable>i</span> (<span class=variable>loop</span> (<span class=variable>+</span> <span class=variable>i</span> <span class=selfeval>1</span>)))))))
</pre><p></p>
<p>
</p>

<p class=noindent>所以 <code class=scheme>(<span class=variable>number-between</span> <span class=selfeval>1</span> <span class=selfeval>6</span>)</code> 将会首先产生 1。如果失败了，<code class=scheme><span class=variable>loop</span></code> 迭代，产生 2。如果又失败了，产生 3，之后类推，直到 6。在 6 以后，<code class=scheme><span class=variable>loop</span></code> 是 7，已经大于 6，调用 <code class=scheme>(<span class=keyword>amb</span>)</code>，它导致最终的失败。（单独的 <code class=scheme>(<span class=keyword>amb</span>)</code> 肯定是失败的。）这时，包含 <code class=scheme>(<span class=variable>number-between</span> <span class=selfeval>1</span> <span class=selfeval>6</span>)</code> 的程序将会回溯到前一个时序的 <code class=scheme><span class=keyword>amb</span></code> 调用，然后以另一种方式尽量满足那个调用。</p>
<p>一定失败的 <code class=scheme>(<span class=keyword>amb</span>)</code> 可以用来实现<em>断言</em>。</p>
<p>
</p>
<pre class=scheme>(<span class=keyword>define</span> <span class=variable>assert</span>
  (<span class=keyword>lambda</span> (<span class=variable>pred</span>)
    (<span class=keyword>if</span> (<span class=variable>not</span> <span class=variable>pred</span>) (<span class=keyword>amb</span>))))
</pre><p></p>
<p>
</p>

<p class=noindent><code class=scheme>(<span class=variable>assert</span> <span class=variable>pred</span>)</code> 调用把 <code class=scheme><span class=variable>pred</span></code> 当作真。否则它将导致当前一定失败的 <code class=scheme><span class=keyword>amb</span></code> 执行。<a name="node_call_footnote_Temp_9"></a><sup><small><a href="#node_footnote_Temp_9">1</a></small></sup></p>

<p>下面是一个使用 <code class=scheme><span class=variable>assert</span></code> 来产生一个小于或等于参数 <code class=scheme><span class=variable>hi</span></code> 的素数的过程：</p>
<p>
</p>
<pre class=scheme>(<span class=keyword>define</span> <span class=variable>gen-prime</span>
  (<span class=keyword>lambda</span> (<span class=variable>hi</span>)
    (<span class=keyword>let</span> ((<span class=variable>i</span> (<span class=variable>number-between</span> <span class=selfeval>2</span> <span class=variable>hi</span>)))
      (<span class=variable>assert</span> (<span class=variable>prime?</span> <span class=variable>i</span>))
      <span class=variable>i</span>)))
</pre><p></p>
<p>
</p>

<p class=noindent>它看上去相当简单，除了在调用时给程序一个任意数（比如 20），它将返回无趣的第一个结果，也就是 2。</p>
<p>我们当然想要得到<em>全部</em>结果，不只是第一个。在这个例子中，我们想得到小于 20 的<em>全部</em>素数。一种办法是在程序得到第一个解之后显示地调用失败继续。所以，</p>
<p>
</p>
<pre class=scheme>(<span class=keyword>amb</span>)
<span class=keyword>=&gt;</span> <span class=selfeval>3</span>
</pre><p></p>
<p>
</p>

<p class=noindent>它也存下了另外一个失败继续，再次调用又可以得到另一个解：</p>
<p>
</p>
<pre class=scheme>(<span class=keyword>amb</span>)
<span class=keyword>=&gt;</span> <span class=selfeval>5</span>
</pre><p></p>
<p>
</p>

<p class=noindent>这种方法的问题是程序是在 Scheme 提示符下调用的，成功返回的解也是通过在提示符中调用 <code class=scheme><span class=keyword>amb</span></code> 得到的。实际上，我们使用不同的程序（不知有多少！），它们把信息从前一个传递给后一个。我们将设法把这些结果作为一个形式的返回值，而我们可以在任何上下文调用这个形式。最终，我们定义 <code class=scheme><span class=keyword>bag-of</span></code> 宏，它返回参数的所有成功解（如果参数不成功，<code class=scheme><span class=keyword>bag-of</span></code> 返回空表）。所以，我们可以使用</p>
<p>
</p>
<pre class=scheme>(<span class=keyword>bag-of</span>
  (<span class=variable>gen-prime</span> <span class=selfeval>20</span>))
</pre><p></p>
<p>
</p>

<p class=noindent>它将返回</p>
<p>
</p>
<pre class=scheme>(<span class=selfeval>2</span> <span class=selfeval>3</span> <span class=selfeval>5</span> <span class=selfeval>7</span> <span class=selfeval>11</span> <span class=selfeval>13</span> <span class=selfeval>17</span> <span class=selfeval>19</span>)
</pre><p></p>
<p>
</p>

<p class=noindent><code class=scheme><span class=keyword>bag-of</span></code> 宏如下定义：</p>
<p>
</p>
<pre class=scheme>(<span class=keyword>define-macro</span> <span class=keyword>bag-of</span>
  (<span class=keyword>lambda</span> (<span class=variable>e</span>)
    <span class=keyword>`</span>(<span class=keyword>let</span> ((<span class=variable>+prev-amb-fail</span> <span class=variable>amb-fail</span>)
           (<span class=variable>+results</span> <span class=keyword>'</span>()))
       (<span class=keyword>if</span> (<span class=variable>call/cc</span>
            (<span class=keyword>lambda</span> (<span class=variable>+k</span>)
              (<span class=keyword>set!</span> <span class=variable>amb-fail</span> (<span class=keyword>lambda</span> () (<span class=variable>+k</span> <span class=selfeval>#f</span>)))
              (<span class=keyword>let</span> ((<span class=variable>+v</span> <span class=keyword>,</span><span class=variable>e</span>))
                (<span class=keyword>set!</span> <span class=variable>+results</span> (<span class=variable>cons</span> <span class=variable>+v</span> <span class=variable>+results</span>))
                (<span class=variable>+k</span> <span class=selfeval>#t</span>))))
           (<span class=variable>amb-fail</span>))
       (<span class=keyword>set!</span> <span class=variable>amb-fail</span> <span class=variable>+prev-amb-fail</span>)
       (<span class=variable>reverse!</span> <span class=variable>+results</span>))))
</pre><p></p>
<p>
</p>

<p class=noindent><code class=scheme><span class=keyword>bag-of</span></code> 首先把它的入口 <code class=scheme><span class=variable>amb-fail</span></code> 保存起来。然后把 <code class=scheme><span class=variable>amb-fail</span></code> 重定义为在 <code class=scheme><span class=keyword>if</span></code> 测试中创建的局部继续 <code class=scheme><span class=variable>+k</span></code>。在测试中，<code class=scheme><span class=keyword>bag-of</span></code> 参数 <code class=scheme><span class=variable>e</span></code> 被求值。如果 <code class=scheme><span class=variable>e</span></code> 成功，它的结果被存到一个叫 <code class=scheme><span class=variable>+results</span></code> 的表的，然后局部继续使用 <code class=scheme><span class=selfeval>#t</span></code> 作为参数被调用。这使得 <code class=scheme><span class=keyword>if</span></code> 测试成功，也使得 <code class=scheme><span class=variable>e</span></code> 在它的下一个回溯点被<em>再次使用</em>。<code class=scheme><span class=variable>e</span></code> 的更多结果也是通过这个方法得到，所有的结果都被存到 <code class=scheme><span class=variable>+results</span></code> 中。</p>
<p>最终，当 <code class=scheme><span class=variable>e</span></code> 失败的时候，将会调用 <code class=scheme><span class=variable>amb-fail</span></code>，它仅仅是 <code class=scheme><span class=selfeval>#f</span></code> 值的局部继续。这个过程跳过了 <code class=scheme><span class=keyword>if</span></code>。我们重新把 <code class=scheme><span class=variable>amb-fail</span></code> 更新为前一个入口的值，然后返回 <code class=scheme><span class=variable>+results</span></code>。（<code class=scheme><span class=variable>reverse!</span></code> 只是把结果按照它们的产生的顺序重排。）</p>
<p>
<a name="node_idx_472"></a></p>
<a name="node_sec_14.4"></a>
<h2 class=section><a href="t-y-scheme-Z-H-1.html#node_toc_node_sec_14.4">14.4&nbsp;&nbsp;逻辑谜题</a></h2>
<p>在解决逻辑谜题的时候，深度优先搜索与回溯结合的威力才显示出来。这些问题若使用一般程序非常困难，但可以使用 <code class=scheme><span class=keyword>amb</span></code> 在保持解决谜题其巨大魅力的同时，简洁明了地来完成。</p>
<p>
</p>
<a name="node_sec_14.4.1"></a>
<h3 class=section><a href="t-y-scheme-Z-H-1.html#node_toc_node_sec_14.4.1">14.4.1&nbsp;&nbsp;Kalotan 谜题</a></h3>
<p>Kalotans 是一个有罕见的怪癖的部落。<a name="node_call_footnote_Temp_10"></a><sup><small><a href="#node_footnote_Temp_10">2</a></small></sup>  他们的男性只说真话，而女性从不说两句连续的真话，也不说两句连续的假话。</p>
<p>一个人类学家（让我们称他为 Worf 吧）去研究他们。Worf 不知道 Kalotan 的语言。一天，他碰到了一对（异性恋的）夫妻和他们的孩子（Kibi）。Worf 问 Kibi：“你是男孩儿吗？”Kibi 使用 Kalotan 语言回答，自然回答的内容 Worf 并未听懂。</p>
<p>Worf 去向孩子的父母（他们懂英语）求解释。一个人说：“Kibi 说‘我是男孩’。”另一个补充道：“Kibi 是女孩。Kibi 说谎了。”
<p>求上面说话者与 Kibi 的性别。</p>
<p>
</p>
<div align=center>&nbsp;&#8212;&nbsp;</div>
<p>结果存在于引入一系列变量，并允许在它们的值中做出选择，把它们的条件枚举为一系列 <code class=scheme><span class=variable>assert</span></code> 表达式。</p>
<p>变量： <code class=scheme><span class=variable>parent1</span></code>，<code class=scheme><span class=variable>parent2</span></code> 和 <code class=scheme><span class=variable>kibi</span></code> 是父母（按出场顺序）与 Kibi 的性别；<code class=scheme><span class=variable>kibi-self-desc</span></code> 是 Kibi 声称的性别（使用 Kalotan 说的）；<code class=scheme><span class=variable>kibi-lied?</span></code> 是布尔值，表明 Kibi 的话是否是一个谎话。</p>
<p>
</p>
<pre class=scheme>(<span class=keyword>define</span> <span class=variable>solve-kalotan-puzzle</span>
  (<span class=keyword>lambda</span> ()
    (<span class=keyword>let</span> ((<span class=variable>parent1</span> (<span class=keyword>amb</span> <span class=keyword>'</span><span class=variable>m</span> <span class=keyword>'</span><span class=variable>f</span>))
          (<span class=variable>parent2</span> (<span class=keyword>amb</span> <span class=keyword>'</span><span class=variable>m</span> <span class=keyword>'</span><span class=variable>f</span>))
          (<span class=variable>kibi</span> (<span class=keyword>amb</span> <span class=keyword>'</span><span class=variable>m</span> <span class=keyword>'</span><span class=variable>f</span>))
          (<span class=variable>kibi-self-desc</span> (<span class=keyword>amb</span> <span class=keyword>'</span><span class=variable>m</span> <span class=keyword>'</span><span class=variable>f</span>))
          (<span class=variable>kibi-lied?</span> (<span class=keyword>amb</span> <span class=selfeval>#t</span> <span class=selfeval>#f</span>)))
      (<span class=variable>assert</span>
       (<span class=variable>distinct?</span> (<span class=variable>list</span> <span class=variable>parent1</span> <span class=variable>parent2</span>)))
      (<span class=variable>assert</span>
       (<span class=keyword>if</span> (<span class=variable>eqv?</span> <span class=variable>kibi</span> <span class=keyword>'</span><span class=variable>m</span>)
           (<span class=variable>not</span> <span class=variable>kibi-lied?</span>)))
      (<span class=variable>assert</span>
       (<span class=keyword>if</span> <span class=variable>kibi-lied?</span>
           (<span class=variable>xor</span>
            (<span class=keyword>and</span> (<span class=variable>eqv?</span> <span class=variable>kibi-self-desc</span> <span class=keyword>'</span><span class=variable>m</span>)
                 (<span class=variable>eqv?</span> <span class=variable>kibi</span> <span class=keyword>'</span><span class=variable>f</span>))
            (<span class=keyword>and</span> (<span class=variable>eqv?</span> <span class=variable>kibi-self-desc</span> <span class=keyword>'</span><span class=variable>f</span>)
                 (<span class=variable>eqv?</span> <span class=variable>kibi</span> <span class=keyword>'</span><span class=variable>m</span>)))))
      (<span class=variable>assert</span>
       (<span class=keyword>if</span> (<span class=variable>not</span> <span class=variable>kibi-lied?</span>)
           (<span class=variable>xor</span>
            (<span class=keyword>and</span> (<span class=variable>eqv?</span> <span class=variable>kibi-self-desc</span> <span class=keyword>'</span><span class=variable>m</span>)
                 (<span class=variable>eqv?</span> <span class=variable>kibi</span> <span class=keyword>'</span><span class=variable>m</span>))
            (<span class=keyword>and</span> (<span class=variable>eqv?</span> <span class=variable>kibi-self-desc</span> <span class=keyword>'</span><span class=variable>f</span>)
                 (<span class=variable>eqv?</span> <span class=variable>kibi</span> <span class=keyword>'</span><span class=variable>f</span>)))))
      (<span class=variable>assert</span>
       (<span class=keyword>if</span> (<span class=variable>eqv?</span> <span class=variable>parent1</span> <span class=keyword>'</span><span class=variable>m</span>)
           (<span class=keyword>and</span>
            (<span class=variable>eqv?</span> <span class=variable>kibi-self-desc</span> <span class=keyword>'</span><span class=variable>m</span>)
            (<span class=variable>xor</span>
             (<span class=keyword>and</span> (<span class=variable>eqv?</span> <span class=variable>kibi</span> <span class=keyword>'</span><span class=variable>f</span>)
                  (<span class=variable>eqv?</span> <span class=variable>kibi-lied?</span> <span class=selfeval>#f</span>))
             (<span class=keyword>and</span> (<span class=variable>eqv?</span> <span class=variable>kibi</span> <span class=keyword>'</span><span class=variable>m</span>)
                  (<span class=variable>eqv?</span> <span class=variable>kibi-lied?</span> <span class=selfeval>#t</span>))))))
      (<span class=variable>assert</span>
       (<span class=keyword>if</span> (<span class=variable>eqv?</span> <span class=variable>parent1</span> <span class=keyword>'</span><span class=variable>f</span>)
           (<span class=keyword>and</span>
            (<span class=variable>eqv?</span> <span class=variable>kibi</span> <span class=keyword>'</span><span class=variable>f</span>)
            (<span class=variable>eqv?</span> <span class=variable>kibi-lied?</span> <span class=selfeval>#t</span>))))
      (<span class=variable>list</span> <span class=variable>parent1</span> <span class=variable>parent2</span> <span class=variable>kibi</span>))))
</pre><p></p>
<p>
</p>

<p class=noindent>注意那个辅助过程：过程 <code class=scheme><span class=variable>distinct?</span></code> 返回真值的条件是参数表中的每个元素都是不同的，否则返回假。过程 <code class=scheme><span class=variable>xor</span></code> 返回真值的条件是它的两个参数只有一个为真，否则返回假。</p>
<p>输入 <code class=scheme>(<span class=variable>solve-kalotan-puzzle</span>)</code> 就可以解决这个谜题。</p>
<p>
</p>
<a name="node_sec_14.4.2"></a>
<h3 class=section><a href="t-y-scheme-Z-H-1.html#node_toc_node_sec_14.4.2">14.4.2&nbsp;&nbsp;地图着色问题</a></h3>
<p>很早以前我们就知道（直到 1976&nbsp;[<a href="t-y-scheme-Z-H-24.html#node_bib_29">29</a>] 年才得证）四个颜色就足以为世界地图着色 &#8212; 也就是说，为相邻国家填不同的颜色。实际上进行着色依然是一项艰巨的任务，下面的程序将展现不确定性编程如何有帮助。</p>
<p>下面的程序解决欧洲西部的地图着色问题。问题和一个 Prolog 解决方案在 <em>The Art of
    Prolog</em> [<a href="t-y-scheme-Z-H-24.html#node_bib_31">31</a>] 中给出。（将我们的解决方案和书中的作比较将会大有裨益。）</p>
<p>
</p>
<p>过程 <code class=scheme><span class=variable>choose-color</span></code> 不确定地返回四色之一</p>
<p>
</p>
<pre class=scheme>(<span class=keyword>define</span> <span class=variable>choose-color</span>
  (<span class=keyword>lambda</span> ()
    (<span class=keyword>amb</span> <span class=keyword>'</span><span class=variable>red</span> <span class=keyword>'</span><span class=variable>yellow</span> <span class=keyword>'</span><span class=variable>blue</span> <span class=keyword>'</span><span class=variable>white</span>)))
</pre><p></p>
<p>
</p>

<p class=noindent>在我们的解决方案中，我们为每个国家建立一个数据结构。这个数据结构是一个 3 个元素的表：表中第一个元素是国家名字；第二个元素是所上的颜色；第三个是它邻国的颜色。注意我们使用国家的首字母作为颜色变量 <a name="node_call_footnote_Temp_11"></a><sup><small><a href="#node_footnote_Temp_11">3</a></small></sup>。比如，Belguim 表为 <code class=scheme>(<span class=variable>list</span> <span class=keyword>'</span><span class=variable>belgium</span> <span class=variable>b</span> (<span class=variable>list</span> <span class=variable>f</span> <span class=variable>h</span> <span class=variable>l</span> <span class=variable>g</span>))</code>，因为 &#8212; 按照问题描述 &#8212; Belguim 的邻国是 France，Holland，Luxembourg 和 Germany。</p>
<p>一旦我们为每个国家都创建了表，我们规定了（唯一的！）它们必须要满足的条件，即没有国家能够上它邻国的颜色。也就是说，对每个国家表，第二个元素一定不能在第三个元素中。</p>
<p>
</p>
<pre class=scheme>(<span class=keyword>define</span> <span class=variable>color-europe</span>
  (<span class=keyword>lambda</span> ()

    <span class=comment>;choose colors for each country</span>
    (<span class=keyword>let</span> ((<span class=variable>p</span> (<span class=variable>choose-color</span>)) <span class=comment>;Portugal</span>
          (<span class=variable>e</span> (<span class=variable>choose-color</span>)) <span class=comment>;Spain</span>
          (<span class=variable>f</span> (<span class=variable>choose-color</span>)) <span class=comment>;France</span>
          (<span class=variable>b</span> (<span class=variable>choose-color</span>)) <span class=comment>;Belgium</span>
          (<span class=variable>h</span> (<span class=variable>choose-color</span>)) <span class=comment>;Holland</span>
          (<span class=variable>g</span> (<span class=variable>choose-color</span>)) <span class=comment>;Germany</span>
          (<span class=variable>l</span> (<span class=variable>choose-color</span>)) <span class=comment>;Luxemb</span>
          (<span class=variable>i</span> (<span class=variable>choose-color</span>)) <span class=comment>;Italy</span>
          (<span class=variable>s</span> (<span class=variable>choose-color</span>)) <span class=comment>;Switz</span>
          (<span class=variable>a</span> (<span class=variable>choose-color</span>)) <span class=comment>;Austria</span>
          )

      <span class=comment>;construct the adjacency list for</span>
      <span class=comment>;each country: the 1st element is</span>
      <span class=comment>;the name of the country; the 2nd</span>
      <span class=comment>;element is its color; the 3rd</span>
      <span class=comment>;element is the list of its</span>
      <span class=comment>;neighbors' colors</span>
      (<span class=keyword>let</span> ((<span class=variable>portugal</span>
             (<span class=variable>list</span> <span class=keyword>'</span><span class=variable>portugal</span> <span class=variable>p</span>
                   (<span class=variable>list</span> <span class=variable>e</span>)))
            (<span class=variable>spain</span>
             (<span class=variable>list</span> <span class=keyword>'</span><span class=variable>spain</span> <span class=variable>e</span>
                   (<span class=variable>list</span> <span class=variable>f</span> <span class=variable>p</span>)))
            (<span class=variable>france</span>
             (<span class=variable>list</span> <span class=keyword>'</span><span class=variable>france</span> <span class=variable>f</span>
                   (<span class=variable>list</span> <span class=variable>e</span> <span class=variable>i</span> <span class=variable>s</span> <span class=variable>b</span> <span class=variable>g</span> <span class=variable>l</span>)))
            (<span class=variable>belgium</span>
             (<span class=variable>list</span> <span class=keyword>'</span><span class=variable>belgium</span> <span class=variable>b</span>
                   (<span class=variable>list</span> <span class=variable>f</span> <span class=variable>h</span> <span class=variable>l</span> <span class=variable>g</span>)))
            (<span class=variable>holland</span>
             (<span class=variable>list</span> <span class=keyword>'</span><span class=variable>holland</span> <span class=variable>h</span>
                   (<span class=variable>list</span> <span class=variable>b</span> <span class=variable>g</span>)))
            (<span class=variable>germany</span>
             (<span class=variable>list</span> <span class=keyword>'</span><span class=variable>germany</span> <span class=variable>g</span>
                   (<span class=variable>list</span> <span class=variable>f</span> <span class=variable>a</span> <span class=variable>s</span> <span class=variable>h</span> <span class=variable>b</span> <span class=variable>l</span>)))
            (<span class=variable>luxembourg</span>
             (<span class=variable>list</span> <span class=keyword>'</span><span class=variable>luxembourg</span> <span class=variable>l</span>
                   (<span class=variable>list</span> <span class=variable>f</span> <span class=variable>b</span> <span class=variable>g</span>)))
            (<span class=variable>italy</span>
             (<span class=variable>list</span> <span class=keyword>'</span><span class=variable>italy</span> <span class=variable>i</span>
                   (<span class=variable>list</span> <span class=variable>f</span> <span class=variable>a</span> <span class=variable>s</span>)))
            (<span class=variable>switzerland</span>
             (<span class=variable>list</span> <span class=keyword>'</span><span class=variable>switzerland</span> <span class=variable>s</span>
                   (<span class=variable>list</span> <span class=variable>f</span> <span class=variable>i</span> <span class=variable>a</span> <span class=variable>g</span>)))
            (<span class=variable>austria</span>
             (<span class=variable>list</span> <span class=keyword>'</span><span class=variable>austria</span> <span class=variable>a</span>
                   (<span class=variable>list</span> <span class=variable>i</span> <span class=variable>s</span> <span class=variable>g</span>))))
        (<span class=keyword>let</span> ((<span class=variable>countries</span>
               (<span class=variable>list</span> <span class=variable>portugal</span> <span class=variable>spain</span>
                     <span class=variable>france</span> <span class=variable>belgium</span>
                     <span class=variable>holland</span> <span class=variable>germany</span>
                     <span class=variable>luxembourg</span>
                     <span class=variable>italy</span> <span class=variable>switzerland</span>
                     <span class=variable>austria</span>)))

          <span class=comment>;the color of a country</span>
          <span class=comment>;should not be the color of</span>
          <span class=comment>;any of its neighbors</span>
          (<span class=variable>for-each</span>
           (<span class=keyword>lambda</span> (<span class=variable>c</span>)
             (<span class=variable>assert</span>
              (<span class=variable>not</span> (<span class=variable>memq</span> (<span class=variable>cadr</span> <span class=variable>c</span>)
                         (<span class=variable>caddr</span> <span class=variable>c</span>)))))
           <span class=variable>countries</span>)

          <span class=comment>;output the color</span>
          <span class=comment>;assignment</span>
          (<span class=variable>for-each</span>
           (<span class=keyword>lambda</span> (<span class=variable>c</span>)
             (<span class=variable>display</span> (<span class=variable>car</span> <span class=variable>c</span>))
             (<span class=variable>display</span> <span class=selfeval>&quot; &quot;</span>)
             (<span class=variable>display</span> (<span class=variable>cadr</span> <span class=variable>c</span>))
             (<span class=variable>newline</span>))
           <span class=variable>countries</span>))))))
</pre><p></p>
<p>
</p>

<p class=noindent>输入 <code class=scheme>(<span class=variable>color-europe</span>)</code> 来得到一个颜色分配。</p>
<p>
</p>
<div class=footnoterule><hr></div><p></p>
<div class=footnote><p><a name="node_footnote_Temp_9"></a><sup><small><a href="#node_call_footnote_Temp_9">1</a></small></sup> SICP 把这个过程叫做 <code class=scheme><span class=variable>require</span></code>。我们使用标识 <code class=scheme><span class=variable>assert</span></code> 是为了避免在其它情况下不正式使用标识 <code class=scheme><span class=variable>require</span></code> 的时候出现困惑，也即它用作一个载入代码模块的运算符的时候。</p>
<p><a name="node_footnote_Temp_10"></a><sup><small><a href="#node_call_footnote_Temp_10">2</a></small></sup> 这个谜题归功于 Hunter [<a href="t-y-scheme-Z-H-24.html#node_bib_19">19</a>].</p>
<p><a name="node_footnote_Temp_11"></a><sup><small><a href="#node_call_footnote_Temp_11">3</a></small></sup> Spain (Espa&ntilde;a) 中有 <code class=scheme><span class=variable>e</span></code>，避免和 Switzerland 的冲突。</p>
</div>
<div class=smallskip></div>
<p style="margin-top: 0pt; margin-bottom: 0pt">
<div align=right class=navigation>[Go to <span><a href="t-y-scheme.html">first</a>, <a href="t-y-scheme-Z-H-15.html">previous</a></span><span>, <a href="t-y-scheme-Z-H-17.html">next</a></span> page<span>; &nbsp;&nbsp;</span><span><a href="t-y-scheme-Z-H-1.html#node_toc_start">contents</a></span><span><span>; &nbsp;&nbsp;</span><a href="t-y-scheme-Z-H-25.html#node_index_start">index</a></span>]</div>
</p>
<p></p>
</div>
</body>
</html>
